闲扯
动态点分治的常数是真的大。。。
题面
Solution
这道题有两种思路:
树链剖分+动态开店点线段树
先写出答案要求的式子:
其中,我们设 $dis_u$ 表示 $u$ 到根结点的距离, $sum_dis=\sum_{i=1}^ndis_i$ 。
然后我们只需要解决 $\sum dis_{lca_{u,i}}$ 即可。
然而这是一个经典问题,直接用树剖维护即可。
由于题目要求 $[L,R]$ 之间的答案,所以我们用主席树求解即可。(不过貌似有点卡空间,需要用到标记永久化,不过不太会,就没写)
动态点分治
动态点分治经典题目。
先建出点分树,然后考虑怎么维护。
套路性的,我们维护 $dis1_u,dis2_u,sum_u$ 分别表示点 $u$ 的子树中的点到 $u$ 的距离,到 $fa_u$ 的距离,以及点的个数。
根据点分树的性质,我们可以得到空间占用为 $n\log n$ 级别。
如果不考虑 $[L,R]$ 的限制,我们直接计算即可(方法与换根 $DP$ 类似)。
但是现在有了 $L,R$ 的限制,考虑怎么做。
我们可以将上面的三组变量存在 $vector$ 里面,同时用 $pair$ 记录下对应的颜色。
然后我们将它们按照颜色从小到大排序,然后求一个前缀和。
在在询问时,我们二分出有用的区间即可。
点分树暴力跳 $fa$ 复杂度为 $O(n\log n)$ ,每个点查询贡献复杂度为 $O(\log n)$ ,总复杂度为 $O(n\log^2 n)$ 。
Code
1 |
|